#include <bits/stdc++.h>

using namespace std;

const int maxn=100005;
char str[maxn];
int ssa[2][maxn*2],rrk[2][maxn*2];
int cnt[maxn],h[maxn];
int n,k;

void calsa(int *sa,int *rk,int *Sa,int *Rk){
	for(int i=1;i<=n;i++) cnt[rk[sa[i]]]=i;
	for(int i=n;i>=1;i--)
		if(sa[i]>k)
			Sa[cnt[rk[sa[i]-k]]--]=sa[i]-k;
	for(int i=n-k+1;i<=n;i++) Sa[cnt[rk[i]]--]=i;
	for(int i=1;i<=n;i++) Rk[Sa[i]]=Rk[Sa[i-1]]+(rk[Sa[i]]!=rk[Sa[i-1]]||rk[Sa[i]+k]!=rk[Sa[i-1]+k]);
}

int main(){
	int p,q;
	scanf("%s",str+1);
	n=strlen(str+1);

	memset(cnt,0,sizeof cnt);
	for(int i=1;i<=n;i++) cnt[str[i]]++;
	for(int i=1;i<256;i++) cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--) ssa[0][cnt[str[i]]--]=i;
	for(int i=1;i<=n;i++) rrk[0][ssa[0][i]]=rrk[0][ssa[0][i-1]]+(str[ssa[0][i]]!=str[ssa[0][i-1]]);

	k=1;p=0;q=1;
	while(k<n){
		calsa(ssa[p],rrk[p],ssa[q],rrk[q]);
		k<<=1;swap(p,q);
	}

	int *rk=rrk[p],*sa=ssa[p];
	int k=0;
	for(int i=1;i<=n;i++){
		if(k) k--;
		if(rk[i]-1<1) continue;
		int j=sa[rk[i]-1];
		while(str[i+k]==str[j+k]) k++;
		h[rk[i]]=k;
	}

	for(int i=1;i<=n;i++) printf("%d ",sa[i]);putchar('\n');
	for(int i=2;i<=n;i++) printf("%d ",h[i]);putchar('\n');

	return 0;
}